|
In graph theory, the meshedness coefficient is a graph invariant of planar graphs that measures the number of bounded faces of the graph, as a fraction of the possible number of faces for other planar graphs with the same number of vertices. It ranges from 0 for trees to 1 for maximal planar graphs.〔 〕 〔 〕 ==Definition== The meshedness coefficient is used to compare the general cycle structure of a connected planar graph to two extreme relevant references. In one end, there are trees, planar graphs with no cycle.〔 The other extreme is represented by maximal planar graphs, planar graphs with the highest possible number of edges and faces for a given number of vertices. The normalized meshedness coefficient is the ratio of available face cycles to the maximum possible number of face cycles in the graph. This ratio is 0 for a tree and 1 for any maximal planar graph. More generally, it can be shown using the Euler characteristic that all ''n''-vertex planar graphs have at most 2''n'' − 5 bounded faces (not counting the one unbounded face) and that if there are ''m'' edges then the number of bounded faces is ''m'' − ''n'' + 1 (the same as the circuit rank of the graph). Therefore, a normalized meshedness coefficient can be defined as the ratio of these two numbers: : It varies from 0 for trees to 1 for maximal planar graphs. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Meshedness coefficient」の詳細全文を読む スポンサード リンク
|